package list;

public class LeetCode19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        Recursion recursion = new Recursion();
        return recursion.removeNthFromEnd(head, n);
    }

    /**
     * 双指针解法
     * 快指针先走n步后, 慢指针再出发
     * 当快指针走到终点时, 满指针所在的位置就是倒数第n个节点
     * 删除节点需要该节点的前一个节点, 所以需要找到倒数第n+1个节点
     */
    static class DoublePointer {

        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(-1, head);
            ListNode x = find(dummy, n + 1);
            x.next = x.next.next;
            return dummy.next;
        }

        public ListNode find(ListNode head, int n) {
            ListNode p1 = head;
            ListNode p2 = head;
            while (p1 != null) {
                if (n <= 0) {
                    p2 = p2.next;
                }
                p1 = p1.next;
                n--;
            }
            return p2;
        }
    }

    /**
     * 递归解法
     * 由于递归的倒序执行特性, 可以很方便的找到倒数第n个节点
     */
    static class Recursion {

        int n;
        ListNode x;

        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(-1, head);
            this.n = n + 1;
            find(dummy);
            x.next = x.next.next;
            return dummy.next;
        }

        public void find(ListNode node) {
            if (node == null) {
                return;
            }
            find(node.next);
            if (n == 1) {
                x = node;
            }
            n--;
        }
    }

}
